package com.zjsru.plan2025.normal;

import java.util.Arrays;

/**
 * 2563. 统计公平数对的数目
 * @Author: cookLee
 * @Date: 2025-04-20
 */
public class CountFairPairs {

    /**
     * 主
     * \
     * 输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
     * 输出：6
     * 解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
     * \
     * 输入：nums = [1,7,9,2,5], lower = 11, upper = 11
     * 输出：1
     * 解释：只有单个公平数对：(2,3) 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CountFairPairs countFairPairs = new CountFairPairs();
        System.out.println(countFairPairs.countFairPairs(new int[]{0, 1, 7, 4, 4, 5}, 3, 6));
    }

    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            //当前下标元素下满足的总元素格数
            int right = this.helper(upper - nums[i] + 1, nums, i);
            int left = this.helper(lower - nums[i], nums, i);
            ans += right - left;
        }
        return ans;
    }

    private int helper(int curr, int[] nums, int right) {
        int left = -1;
        while (left + 1 < right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] < curr) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }
}
